Vùng đất tỉnh Cao Bằng bắt đầu thuộc lãnh thổ Việt Nam vào năm 1039, khi Lý Thái Tông đánh thủ lĩnh châu Thảng Do và châu Quảng Nguyên (sau này là huyện Quảng Uyên) là Nùng Tồn Phúc.

Năm 1041 vợ A Nùng và con trai của Tồn Phúc là Nùng Trí Cao từ động Lôi Hỏa (Hạ Lôi, nay là khoảng hương Hạ Lôi huyện Đại Tân địa cấp thị Sùng Tả tỉnh Quảng Tây Trung Quốc, phía đông bắc huyện Trùng Khánh) về chiếm lại 2 châu trên, nhà Lý cử quân lên đánh bắt được Trí Cao nhưng không giết mà cho làm quan nhà Lý cai quản các châu động trên. Nhà Lý gộp thêm các động Vật Dương, động Lôi Hỏa, động Bình An, động Bà Tư (là các động vốn trong số 10 động thuộc quyền cai quản của Tồn Phúc), cùng châu Thảng Do vào đất Quảng Nguyên và gọi chung là châu Quảng Nguyên. Ngoài châu Quảng Nguyên, thì năm 1041, châu Tư Lang (nay là đất 2 huyện Trùng Khánh và Hạ Lang tỉnh Cao Bằng) nằm ở phía đông bắc châu Quảng Nguyên, nhà Lý cũng phụ vào đất cai quản của Trí Cao, coi như đất Đại Cồ Việt vùng Trí Cao cai quản mà sau đó nhà Lý đòi chủ quyền với nhà Tổng gồm 2 châu Tư Lang và Quảng Nguyên (gộp cả Bình An (nay thuộc Cao Bằng), Bà Tư (nay thuộc Cao Bằng), Thảng Do, Lôi Hỏa (phía đông nam Vật Dương), Vật Dương (phía đông Vật Ác), Vật Ác (vùng phía nam trấn An Đức của Tĩnh Tây Quảng Tây ngày nay)). Tuy bề ngoài thần phục nhà Lý, nhưng bên trong Nùng Trí Cao nuôi chí tự cường lập quốc gia độc lập. Năm 1048 Trí Cao lại nổi dậy đánh chiếm động Vật Ác (vùng phía nam An Đức trấn của Tĩnh Tây Trung Quốc ngày nay), vốn thuộc nhà Lý từ năm 1039, nhà Lý đem quân lên đánh. Sau khi gây sự với nhà Lý không thành, Trí Cao đánh chiếm châu An Đức (Ande Zhou 安德州, nay là khoảng địa bàn trấn An Đức của thị xã Tĩnh Tây) và vùng biên giới các tỉnh Quảng Tây, Quảng Đông Trung Quốc. Nhà Tống tiêu diệt quốc gia của Chí Cao năm 1055. Các thủ lĩnh địa phương cai quản châu động kế thừa Trí Cao, không thực sự thần phục nhà Lý, đem một số động thuộc châu Quảng Nguyên (là phần đất phía bắc Cao Bằng ngày nay thuộc thị xã Tĩnh Tây Trung Quốc) sang thần phục nhà Tốngː Nùng Tông Đán (Tông Đản) năm 1049 đem động Vật Ác (sau thuộc Tống bị nhà Tổng đổi thành Thuận An châu, nay là các hương trấn biên giới thuộc thị xã Tĩnh Tây địa cấp thị Bách Sắc khu Tự trị Dân tộc Choang Quảng Tây, nằm ở phía tây nam thị xã Tĩnh Tây tiếp giáp các huyện Hà Quảng, Trà Lĩnh tỉnh Cao Bằng, có thể là vùngː hương Nam Pha, hương Thôn Bàn, hương An Ninh, trấn Long Bang (An Bang),...), Nùng Trí Hội năm 1062 đem động Vật Dương sang Tống (nhà Tống đổi tên thành Quy Hóa châu, nay là các hương trấn phía đông nam thị xã Tĩnh Tây, tiếp giáp huyện Trùng Khánh Cao Bằng, có lẽ làː hương Nhâm Trang (Nhâm Động), trấn Nhạc Vũ, trấn Hồ Nhuận (Nhuận Động), trấn Hóa Động,... Kèm theo đất Vật Dương nhập Tống đợt này, có thể có cả đất động Lôi Hỏa (Hạ Lôi),...). Đến Chiến tranh Tống-Việt, 1075-1077, châu Quảng Nguyên (bao gồm các vùng đất ngày nay là các huyện Hà Quảng, Trà Lĩnh, Quảng Uyên, Hòa An, thành phố Cao Bằng, Phục Hòa), châu Tư Lang (nay là Trùng Khánh, Hạ Lang), cùng các châu nay thuộc Lạng Sơn làː Thất Nguyên (Thất Khê, Tràng Định), Môn (Cao Lộc), Tô Mậu (Đình Lập), bị Quách Quỳ tướng nhà Tống chiếm đóng không trả lại Đại Việt sau chiến tranh (Giai đoạn này châu Quảng Nguyên bị nhà Tống đổi tên thành Thuận châu).

Bằng chiến thuật vừa gây xung đột biên giới (lùng bắt Nùng Trí Hội), vừa ngoại giao triều cống và đàm phán, từ năm 1077 đến năm 1088, vua quan nhà Lý thời Lý Nhân Tông đần thu phục lại gần như hoàn toàn các vùng đất bị nhà Tông chiếm từ nhà Lý trước và trong cuộc chiến Tống - Việt. Kết quả đàm phán của phái đoàn Đào Tông Nguyên sứ thần nhà Lý năm 1079, thu lại được toàn bộ các châu nay là đất Lạng Sơn (là châu Tô Mậu, châu Môn và châu Thất Nguyên), đất nay thuộc Cao Bằng thì thu lại được châu Tư Lang, và phần lớn châu Quảng Nguyên (Thuận châu nhà Tống, phần đất nhà Tống chiếm trong cuộc chiến 1076-1077), trừ phân đất Vật Ác (châu Thuận An nhà Tống), Vật Dương (châu Quy Hóa nhà Tống), Lôi Hỏa mất về nhà Tống trước chiến tranh thì nhà Tống không trả.

Năm 1084, phái đoàn Lê Văn Thịnh sứ thần nhà Lý, tiếp tục sang Bằng Tường Quảng Tây Trung Quốc đàm phán đòi lại đất hai động Vật Dương và Vật Ác từ nhà Tống. Nhưng thay vì trả đất hai động Vật Dương và Vật Ác của châu Quảng Nguyên, thì nhà Tống đổi lại trả cho nhà Lý vùng đất 6 huyệnː Bảo Lạc, Luyện, Miêu (Pác Miêu), Đinh, Phóng, Cận (là đất nay thuộc các huyện Bảo Lạc, Bảo Lâm tỉnh Cao Bằng) cùng 2 động Túc (Tĩnh Túc), Tang (nay là khoảng vùng đất huyện Nguyên Bình Cao Bằng). Các huyện động này vốn là các châu động ki mi nằm kẹp giữa hai nước Lý, Tống, nằm ở phía tây châu Quảng Nguyên, ở phía đông châu Bình Nguyên (Vị Xuyên, Hà Giang). Tuy nhiên, nhà Lý vẫn kiên trì tiếp tục đàm phán đòi đất 2 động Vật Dương, Vật Ác cho đến năm 1088, nhưng không thành công. Từ đó đất 2 động Vật Ác (châu Thuận An nhà Tống), Vật Dương (châu Quy Hóa nhà Tống) vĩnh viễn thuộc Trung Quốc (ngày nay chúng là vùng đất phía nam của thị xã Tĩnh Tây địa cấp thị Bách Sắc khu Tự trị Dân tộc Choang tỉnh Quảng Tây, tiếp giáp biên giới với các huyện Hà Quảng, Trà Lĩnh, và Trùng Khánh của Cao Bằng). Đại Việt sử ký tiền biên, Ngô Thì Sĩ chépː "Giáp Tý năm thứ 9 (1084, Tống Nguyên Phong năm thứ 7) mùa Hạ tháng 6, sai Thị lang bộ Binh là Lê Văn Thịnh sang Tồng bàn việc biên giới. Họp với Hữu giang tuần kiểm nhà Tống là Thành Tác ở Quảng Tây bàn về biên giới Thuận An, Quy Hóa. Văn Thịnh đến nơi, mọi việc đều lựa chiều uốn nắn, không hề biện bác, chỉ từ từ lấy lý mà giảng giải, có câu rằngː "Bồi thần này không dám tranh chấp". Vua Tống nghe tin, ban chiếu cho Văn Thịnh là biết theo ý kính thuận, ban cho áo dài rồi nhân đó trả cho ta 6 huyện thuộc Bảo Lạc, 6 động thuộc Túc Tang ở phía ngoài cửa ải."[8]

Thời Lê sơ, Lê Thánh Tông cho lập thừa tuyên Thái Nguyên (Ninh Sóc), thì Cao Bằng là 1 trong 3 phủ của thừa tuyên Thái Nguyên. Phủ Cao Bằng lúc này gồm 4 châuː Thượng Tư Lang (châu Thượng Lang, nay là huyện Trùng Khánh), Hạ Tư Lang (châu Hạ Lang, nay là huyện Hạ Lang), Quảng Uyên (đổi từ châu Quảng Nguyên, nay là các huyện Quảng Uyên, Phục Hòa), Thạch Lâm (nay là các huyện Hà Quảng, Trà Lĩnh, Thạch An, Hòa An, Nguyên Bình, và thành phố Cao Bằng). Phần phía tây tỉnh Cao Bằng ngày nay lại thuộc thừa tuyên Tuyên Quang là châu Bảo Lạc thuộc phủ Yên Bình, (châu Bảo Lạc nay là đất các huyện Bảo Lạc, Bảo Lâm của tỉnh Cao Bằng).

Năm 1499 niên hiệu Cảnh Thống thứ 2, vua Lê Hiến Tông tách phủ Cao Bằng ra khỏi Thái Nguyên lập thành một trấn riêng mang tên Cao Bằng. Từ đây Cao Bằng trở thành đơn vị hành chính tương đương cấp tỉnh ngày nay. Nên hiện nay, Việt Nam lấy năm 1499 là năm thành lập tỉnh Cao Bằng.[9]. Tuy nhiên, Đào Duy Anh thì cho rằng Cao Bằng chỉ thực sự tách khỏi Thái Nguyên thành một trấn (đơn vị hành chính cấp tỉnh) từ sau khi nhà Mạc bị diệt. Trong cuốn Đất nước Việt Nam qua các đời, Đào Duy Anh viếtː "Phủ Cao Bằngː Nhất thống chí (Cao Bằng) chép rằng đời Lê Quang Thuận là phủ Bắc Bình; đời Hồng Đức mới đổi làm Cao Bình, tức Cao Bằng. Sau khi họ Mạc bị diệt hẳn mới đổi làm trấn Cao Bằng, vẫn lãnh một phủ là phủ Cao Bằng; đầu đời Gia Long đặt trấn thủ; năm thứ 7 (1808) đổi tên phủ làm [phủ] Trùng Khánh, năm Minh Mạng thứ 12 (1831) làm tỉnh Cao Bằng."[10]

Sau khi thất thủ Thăng Long năm 1592, nhà Mạc chạy lên Cao Bằng và xây dựng vùng đất này để chống lại nhà Lê Trịnh cho đến 1677 mới chấm dứt.

Thời Pháp thuộc

Từ năm 1886 – 1945, tên gọi, địa giới và số lượng các đơn vị hành chính tỉnh Cao Bằng luôn có sự thay đổi. Cuối thế kỷ XIX, tỉnh Cao Bằng gồm có phủ Trùng Khánh (với 3 châu: Thượng Lang, Hạ Lang, Quảng Uyên) và phủ Hòa An (với 3 châu: Thạch Lâm, Thạch An, Nguyên Bình).

Tháng 10 năm 1886, thực dân Pháp đánh chiếm Cao Bằng.

Năm 1888, Cao Bằng là một quân khu. Quân khu Cao Bằng gồm Tiểu quân khu Cao Bằng và các đồn binh: Cao Bằng, Sóc Giang, Nguyên Bình, Ngân Sơn, Trà Lĩnh, Trùng Khánh, Hạ Lang, Phục Hoà, Nặm Nàng.

Thực dân Pháp đã phân chia địa bàn từ Thanh Hoá trở ra bắc thành 14 quân khu. Mỗi quân khu do một sĩ quan cấp đại tá hoặc cấp tướng trực tiếp chỉ huy.

Ngày 06/8/1891, Toàn quyền Đông Dương ra nghị định bãi bỏ các quân khu và thiết lập các đạo quan binh. Đạo quan binh là đơn vị hành chính đặc biệt do giới quân sự nắm quyền cai trị. Mỗi đạo quan binh do một sĩ quan đứng đầu làm tư lệnh với đầy đủ quyền dân sự và quân sự, thời kỳ đầu về dân sự ngang với Thống sứ Bắc Kỳ.

Ngày 20/8/1891, Toàn quyền Đông Dương ra nghị định thành lập tại Bắc Kỳ 4 đạo quan binh: Đạo quan binh 1 Phả Lại, Đạo quan binh 2 Lạng Sơn, Đạo quan binh 3 Yên Bái, Đạo quan binh 4 Sơn La. Đạo quan binh thứ 2 thủ phủ đặt tại Cao Bằng (Cao Bằng là tiểu quân khu thuộc Đạo quan binh 2). Sau đó chuyển thành Đạo quan binh 2 Cao Bằng, đạo lỵ đặt tại Cao Bằng, gồm 3 tiểu quân khu: Cao Bằng, Bảo Lạc, Bắc Kạn.

Ngày 01/01/1906, Toàn quyền Đông Dương ra quyết định: "các Đạo quan binh 2, 3 và 4 được đặt lại, về phương diện tài chính dưới quyền của Thống sứ Bắc Kỳ và được cai trị theo luật lệ hiện hành tại các tỉnh dân sự. Việc cai trị các Đạo quan binh 2, 3 và 4 vẫn đặt dưới quyền một sĩ quan cao cấp cấp đại tá hoặc trung tá. Mỗi đạo quan binh được phân thành 2 hạt. Việc chia thành khu vực bị bãi bỏ".

Từ sau Nghị định của Toàn quyền Đông Dương ngày 16/4/1908, đạo quan binh chia thành các đơn vị hành chính và tư pháp ngang với công sứ các tỉnh dân sự.

Năm 1926, theo sách Địa dư các tỉnh Bắc Kỳ, "Cao Bằng là Đạo quan binh thứ nhì" gồm 1 phủ: Hòa An (phủ lỵ ở Nước Hai); 7 châu: Hà Quảng, Thạch An, (châu lỵ ở Đông Khê), Nguyên Bình, Phục Hoà (châu lỵ ở Tà Lùng), Quảng Uyên, Thượng Lang (châu lỵ ở Trùng Khánh phủ) và Hạ Lang; 3 đại lý: Quảng Uyên, Nguyên Bình và Đông Khê.

Sau năm 1945

Năm 1948, Chính phủ quyết định bãi bỏ cấp tổng, phủ, đạo, châu. Cấp trên cấp xã và dưới cấp tỉnh thống nhất gọi là huyện. Tỉnh Cao Bằng lúc đó gồm thị xã Cao Bằng và 10 huyện: Bảo Lạc, Hạ Lang, Hà Quảng, Hòa An, Nguyên Bình, Phục Hòa, Quảng Uyên, Thạch An, Trấn Biên, Trùng Khánh.

Ngày 3 tháng 10 năm 1950, Cao Bằng hoàn toàn được giải phóng khỏi ách thống trị của thực dân Pháp.

Ngày 1 tháng 7 năm 1956, Cao Bằng cùng các tỉnh Bắc Kạn, Lạng Sơn, Thái Nguyên, Tuyên Quang, Hà Giang hợp thành Khu tự trị Việt Bắc.

Ngày 20 tháng 3 năm 1958, huyện Trấn Biên được đổi tên thành huyện Trà Lĩnh.

Ngày 14 tháng 3 năm 1963, thành lập thị trấn Tĩnh Túc trực thuộc tỉnh Cao Bằng theo Quyết định số 26-CP.

Ngày 7 tháng 4 năm 1966, chia huyện Hà Quảng thành hai huyện Hà Quảng và Thông Nông.

Ngày 8 tháng 3 năm 1967, hai huyện Phục Hòa và Quảng Uyên hợp nhất thành huyện Quảng Hòa theo Quyết định số 27-CP.

Ngày 15 tháng 9 năm 1969, giải thể huyện Hạ Lang, nhập vào hai huyện Quảng Hòa và Trùng Khánh theo Quyết định số 176-CP.

Đến ngày 27 tháng 12 năm 1975, Quốc hội nước Việt Nam Dân chủ cộng hoà (khoá V) kỳ họp thứ 2 quyết nghị bỏ cấp khu trong hệ thống các đơn vị hành chính. Tỉnh Cao Bằng và Lạng Sơn hợp nhất thành một tỉnh là Cao Lạng, tỉnh lỵ đặt tại thị xã Cao Bằng.

Ngày 29 tháng 12 năm 1978, tái lập tỉnh Cao Bằng từ tỉnh Cao Lạng, đồng thời nhập hai huyện Ngân Sơn và Chợ Rã của tỉnh Bắc Thái vào tỉnh Cao Bằng theo Nghị quyết của Quốc hội khóa VI, kỳ họp thứ 4. Khi đó tỉnh Cao Bằng có tỉnh lị là thị xã Cao Bằng và 11 huyện: Bảo Lạc, Chợ Rã, Hà Quảng, Hòa An, Ngân Sơn, Nguyên Bình, Quảng Hòa, Thạch An, Thông Nông, Trà Lĩnh, Trùng Khánh.

Ngày 17 tháng 2 năm 1979, quân Trung Quốc chiếm được thị xã Cao Bằng và đã hủy diệt hầu như toàn thị xã, các công trình kiến trúc đã bị phá tan tành, kể cả chùa chiền đền miếu. Khu di tích chủ tịch Hồ Chí Minh tại hang Pác Bó, xã Trường Hà, huyện Hà Quảng cũng bị đặt bom mìn phá sập cửa hang và các di tích của Bác, bức bia đá Bác viết khi vừa trở về Tổ quốc cũng bị nứt làm đôi.

Ngày 1 tháng 9 năm 1981, tái lập huyện Hạ Lang từ các xã đã nhập vào hai huyện Quảng Hòa và Trùng Khánh theo Quyết định số 44-HĐBT ngày 1 tháng 9 năm 1981.[11] Cùng ngày, chuyển thị trấn Tĩnh Túc trực thuộc huyện Nguyên Bình Quyết định số 44-HĐBT.

Ngày 6 tháng 11 năm 1984, huyện Chợ Rã đổi tên thành huyện Ba Bể theo Quyết định số 144-HĐBT.[12]

Cuối năm 1995, tỉnh Cao Bằng có 1 thị xã Cao Bằng và 12 huyện: Ba Bể, Bảo Lạc, Hạ Lang, Hà Quảng, Hòa An, Ngân Sơn, Nguyên Bình, Quảng Hòa, Thạch An, Thông Nông, Trà Lĩnh, Trùng Khánh.

Năm 1996, trả hai huyện Ngân Sơn và Ba Bể về tỉnh Bắc Kạn mới tái lập.

Ngày 25 tháng 9 năm 2000, chia huyện Bảo Lạc thành huyện Bảo Lạc mới và huyện Bảo Lâm theo Nghị định số 52/2000/NĐ-CP.[13]

Ngày 13 tháng 12 năm 2001, tái lập hai huyện Phục Hòa và Quảng Uyên từ huyện Quảng Hòa.[14]

Ngày 25 tháng 8 năm 2012, chuyển thị xã Cao Bằng thành thành phố Cao Bằng theo Nghị quyết 60/NQ-CP.[15]

Ngày 10 tháng 1 năm 2020, sáp nhập huyện Thông Nông vào huyện Hà Quảng.[16]

Ngày 11 tháng 2 năm 2020, sáp nhập huyện Phục Hòa, huyện Quảng Uyên và xã Quốc Toản thuộc huyện Trà Lĩnh thành huyện Quảng Hòa; sáp nhập phần còn lại của huyện Trà Lĩnh vào huyện Trùng Khánh.[17]

Tỉnh Cao Bằng có 1 thành phố và 9 huyện như hiện nay.